// Aloudin (Albert) Akhriev, 1998-2000.

/* include this:
#ifndef  ALIB_ARR_2D_H
#include "yatl/Arr2D.h"
#endif
*/

#ifndef  ALIB_ARR_2D_H
#define  ALIB_ARR_2D_H

#include <vector>
#include <limits>
#include <assert.h>
#include "undef_min_max.h"
#include "cmmtype.h"
#include "cinline.h"

namespace xtd
{
	template <class T> class arr2d_wise_iterator;
	template <class T> class arr2d_wise_const_iterator;
}

namespace YATL
{

inline bool isRange( int v, int bottom, int top) {
	return ( (v)>=(bottom) && (v)<(top) );
}

template<class T1, class T2>
bool HasEqualDim(const T1 & a, const T2 & b)
{
  return (a.Width() == b.Width() && a.Height() == b.Height());
}

//--------------------------------------------------------------------------
// Functions allocate/deallocate 2D array.
//--------------------------------------------------------------------------

///\relates Arr2D
template<class T>
inline T ** AllocArray2D(int nRow, int nCol, T v = T(), bool bInit = true)
{
  assert(nRow > 0 && nCol > 0);

  T ** a = new T* [nRow];
  T *  p = new T [nRow*nCol];

  if (bInit)
    for(int k = nRow*nCol-1; k >= 0; k--)
      p[k] = v;

  for(int r = 0; r < nRow; r++)
    a[r] = p + (r*nCol);
  return a;
}

///\relates Arr2d
template<class T>
inline T ** FreeArray2D(T ** a)
{
  if (a != NULL)
  {
    T * p = a[0];
    if (p != NULL)
      delete [] p;
    delete [] a;
  }
  return NULL;
}

/**\relates Arr2D
 * \brief allocates 2D-arr of dimension cx*cy, and copies into it elements from a starting at (x,y)
 * \param x		start column
 * \param y		start row
 * \param cx	number of result and copy columns
 * \param cy	number of result and copy rows
 */
template<class T>
inline T ** AllocCopySubArray2D(T ** a, int x, int y, int cx, int cy )
{
	assert(x >= 0 && y >= 0 && cx > 0 && cy > 0 );
	T ** res = AllocArray2D( cy, cx, T(), false );
	for( int iy=0 ; iy != cy; ++iy ) {
		for( int ix=0 ; ix != cx; ++ix ) {
			res[iy][ix] = a[iy+y][ix+x];
		}
	}
	return res;
}


////////////////////////////////////////////////////////////////////////////
// 2-D array of items of any type T.
// N O T E:
// 1. column == x,  row == y;
////////////////////////////////////////////////////////////////////////////
template<class T> class Arr2D
{
 protected:
  T ** m_data;     // array's content = scanline pointers + data
  T *  m_externData;// =0 if I controls both scanline pointers and data; otherwise m_data - scanline ptrs; m_externData - data
  int  m_W, m_H;   // width and height
  int  m_size;     // size = width*height

 public:
  typedef T value_type;	
  typedef T* iterator;
  typedef const T* const_iterator;
  typedef xtd::arr2d_wise_iterator<T> witerator;
  typedef xtd::arr2d_wise_const_iterator<T> const_witerator;

  Arr2D();
  Arr2D(int W, int H, T v = T());
  Arr2D(const Arr2D<T> & a);
  /// allocates only scanlines pointers for external rectangular array
  void		ShareData( T* externData, int W, int H );
  ~Arr2D();
  void		ZeroInit();
  void		FastCopy(const Arr2D<T> & a);
  void		Swap( Arr2D<T> &str );
  void		SetColumn(int c, const std::vector<T> & vec);
  void		GetColumn(int c, std::vector<T> & vec);
  void		Reshape(int x, int y, int cx, int cy);
  T *       begin();
  const T * begin() const;
  witerator wbegin();
  const_witerator wbegin() const;
  T *       end();
  const T * end() const;
  bool		IsInside(int x, int y) const;
  void		Clear();
  const T **Data() const;
  T **      Data();
  int		Size() const;
  bool		IsEmpty() const;
  int		Width() const;
  int		Height() const;
  bool		IsSquare() const;
  void		Resize(int W, int H, T v = T(), bool bInit = true);
  Arr2D<T> & operator=(const Arr2D<T> & a);

  T &		At(int x, int y);
  T & operator()(int x, int y);
  const T & At(int x, int y) const;
  const T & operator()(int x, int y) const;
  T &		At(const Point2i &p);
  T & operator()(const Point2i &p);
  const T & At(const Point2i &p) const;
  const T & operator()(const Point2i &p) const;

  void		SetIfIn(int x, int y, const T & value);
  int		Offset(int x, int y) const;
  T & operator[](int n);
  const T & operator[](int n) const;
  T			GetAt(double fx, double fy) const;  // get bilineary interpolated value
  T *		BeginRow(int r);
  const T * BeginRow(int r) const;
  T *		EndRow(int r);
  const T * EndRow(int r) const;
  T *		BeginColumn(int c);
  const T * BeginColumn(int c) const;
  T *		EndColumn(int c);
  const T * EndColumn(int c) const;

  //complex operations
#ifdef __INTEL_COMPILER
  template< class F >
  Arr2D<T>& ScaledAdd( F factor, const Arr2D<T>& src );
#else 
  Arr2D<T>& ScaledAdd( double factor, const Arr2D<T>& src );
#endif
  Point2i	ArgMax() const;
  Point2i	ArgMin() const;
};

////////////////////////////////////////////////////////////////////////////
// Inlines.
////////////////////////////////////////////////////////////////////////////

  template<class T>
  inline T *       Arr2D<T>::begin()       { return m_data[0]; }

  template<class T>
  inline const T * Arr2D<T>::begin() const { return m_data[0]; }

  template<class T>
  inline typename Arr2D<T>::witerator Arr2D<T>::wbegin()
  {
	  return xtd::arr2d_wise_iterator<T>(*this, 0, 0);
  }

  template<class T>
  inline typename Arr2D<T>::const_witerator Arr2D<T>::wbegin() const
  {
	  return xtd::arr2d_wise_const_iterator<T>(*this, 0, 0);
  }

  template<class T>
  inline T *       Arr2D<T>::end()         { return (m_data[0]+m_size); }

  template<class T>
  inline const T * Arr2D<T>::end()   const { return (m_data[0]+m_size); }

  template<class T>
  inline bool Arr2D<T>::IsInside(int x, int y) const
  { 
    return (isRange(x, 0, m_W) && isRange(y, 0, m_H));
  }


/*  bool IsInside(Point2i p) const
  { 
    return (isRange(p.x, 0, m_W) && isRange(p.y, 0, m_H));
  }*/


  template<class T>
  inline void Arr2D<T>::Clear()
  { 
    m_W = m_H = m_size = 0; 
    if(m_externData==0) {
		FreeArray2D<T>(m_data);
	} else {
		delete[] m_data;
	}
	m_data = 0;
	m_externData = 0;
  }

  template<class T>
  inline const T ** Arr2D<T>::Data() const { return (const T **)m_data; }
  template<class T>
  inline T **       Arr2D<T>::Data()       { return m_data; }
  
  template<class T>
  inline int   Arr2D<T>::Size()     const { return m_size; }

  template<class T>
  inline bool  Arr2D<T>::IsEmpty()  const { return (m_size <= 0); }

  template<class T>
  inline int   Arr2D<T>::Width()    const { return m_W; }

  template<class T>
  inline int   Arr2D<T>::Height()   const { return m_H; }

//  ARect Rect()     const { return ARect(0, 0, m_W, m_H); }

  template<class T>
  inline bool  Arr2D<T>::IsSquare() const { return (m_W == m_H); }


  template<class T>
  inline void Arr2D<T>::Resize(int W, int H, T v, bool bInit)
  {
    if (m_W != W || m_H != H)
    {
		if( m_externData==0 ) {
			FreeArray2D<T>(m_data);
		} else {
			delete[] m_data;
		}
	  m_externData = 0;
      m_data = AllocArray2D<T>(m_H = H, m_W = W, v, bInit);
      m_size = m_W*m_H;
    }
    else if (bInit) std::fill(begin(), end(), v);
  }


  template<class T>
  inline Arr2D<T> & Arr2D<T>::operator=(const Arr2D<T> & a)
  {
    Resize(a.m_W, a.m_H, T(), false);
    if( m_size != 0 ) std::copy(a.begin(), a.end(), begin());
    return (*this);
  }

  template<class T>
  inline T & Arr2D<T>::At(int x, int y)
  {
    assert(isRange(x, 0, m_W) && isRange(y, 0, m_H));
    return m_data[y][x];
  }

  template<class T>
  inline T & Arr2D<T>::operator()(int x, int y) { return At(x,y); }

  template<class T>
  inline const T & Arr2D<T>::At(int x, int y) const
  {
    assert(isRange(x, 0, m_W) && isRange(y, 0, m_H));
    return m_data[y][x];
  }

  template<class T>
  inline const T & Arr2D<T>::operator()(int x, int y) const { return At(x,y); }

  template<class T>
  inline T & Arr2D<T>::At(const Point2i &p) { return At(p.x,p.y); }

  template<class T>
  inline T & Arr2D<T>::operator()(const Point2i &p) { return At(p); }

  template<class T>
  inline const T & Arr2D<T>::At(const Point2i &p) const { return At(p.x,p.y); }

  template<class T>
  inline const T & Arr2D<T>::operator()(const Point2i &p) const { return At(p); }

  template<class T>
  inline void Arr2D<T>::SetIfIn(int x, int y, const T & value)
  {
    if (isRange(x, 0, m_W) && isRange(y, 0, m_H))
      m_data[y][x] = value;
  }

  template<class T>
  inline int Arr2D<T>::Offset(int x, int y) const 
  {
    assert(isRange(x, 0, m_W) && isRange(y, 0, m_H));
    return (x + y*m_W);
  }

  template<class T>
  inline T & Arr2D<T>::operator[](int n)
  {
    assert(isRange(n, 0, m_size));
    return m_data[0][n];
  }

  template<class T>
  inline const T & Arr2D<T>::operator[](int n) const
  {
    assert(isRange(n, 0, m_size));
    return m_data[0][n];
  }

  template<class T>
  inline T Arr2D<T>::GetAt(double fx, double fy) const  // get bilineary interpolated value
  {
    int x = (int)floor(fx);
    int y = (int)floor(fy);

    if (x < 0 || y < 0 || (x+1) >= m_W || (y+1) >= m_H)
      return T();

    float x1 = (float)(fx - x);
    float x0 = (float)(1 - x1);
    float y1 = (float)(fy - y);
    float y0 = (float)(1 - y1);

    return (m_data[y][x]     * (x0 * y0) + 
            m_data[y+1][x]   * (x0 * y1) + 
            m_data[y][x+1]   * (x1 * y0) + 
            m_data[y+1][x+1] * (x1 * y1));
  }

  template<class T>
  inline T * Arr2D<T>::BeginRow(int r)
  {
    assert(isRange(r, 0, m_H));
    return m_data[r];
  }

  template<class T>
  inline const T * Arr2D<T>::BeginRow(int r) const
  {
    assert(isRange(r, 0, m_H));
    return m_data[r];
  }

  template<class T>
  inline T * Arr2D<T>::EndRow(int r)
  {
    assert(isRange(r, 0, m_H));
    return (m_data[r] + m_W);
  }

  template<class T>
  inline const T * Arr2D<T>::EndRow(int r) const
  {
    assert(isRange(r, 0, m_H));
    return (m_data[r] + m_W);
  }

  template<class T>
  inline T * Arr2D<T>::BeginColumn(int c)
  {
    assert(isRange(c, 0, m_W));
    return (m_data[0] + c);
  }

  template<class T>
  inline const T * Arr2D<T>::BeginColumn(int c) const
  {
    assert(isRange(c, 0, m_W));
    return (m_data[0] + c);
  }

  template<class T>
  inline T * Arr2D<T>::EndColumn(int c)
  {
    assert(isRange(c, 0, m_W));
    return (m_data[0] + c + m_size);
  }

  template<class T>
  inline const T * Arr2D<T>::EndColumn(int c) const
  {
    assert(isRange(c, 0, m_W));
    return (m_data[0] + c + m_size);
  }
 
  template<class T>
  inline Arr2D<T>::Arr2D() : m_data(NULL), m_externData(0)
  {
    Clear();
  }

  template<class T>
  inline Arr2D<T>::Arr2D(int W, int H, T v) : m_data(NULL), m_externData(0)
  {
    Clear();
    Resize(W, H, v);
  }

  template<class T>
  inline Arr2D<T>::Arr2D(const Arr2D<T> & a) : m_data(NULL), m_externData(0)
  {
    Clear();
    (*this) = a;
  }

  /// allocates only scanlines pointers for external rectangular array
  template<class T>
  inline void Arr2D<T>::ShareData( T* externData, int W, int H )
  {
    Clear();
	m_externData = externData;
	m_W = W;
	m_H = H;
	m_size = W * H;
	m_data = new T* [H];
	for(int r = 0; r < H; r++) m_data[r] = m_externData + (r*W);
  }

  template<class T>
  inline Arr2D<T>::~Arr2D()
  {
    Clear();
  }

  template<class T>
  inline void Arr2D<T>::ZeroInit()
  { // D A N G E R O U S function! For simple types only!
    if (m_size > 0) memset(begin(), 0, sizeof(T)*m_size);
  }

  template<class T>
  inline void Arr2D<T>::FastCopy(const Arr2D<T> & a)
  { // D A N G E R O U S function! For simple types only!
    Resize(a.m_W, a.m_H, T(), false);
    if (m_size > 0) memcpy(begin(), a.begin(), sizeof(T)*m_size);
  }

  template<class T>
  inline void Arr2D<T>::Swap( Arr2D<T> &str ) {
	  simple_swap( m_data, str.m_data );
	  simple_swap( m_externData, str.m_externData );
	  simple_swap( m_W, str.m_W );
	  simple_swap( m_H, str.m_H );
	  simple_swap( m_size, str.m_size );
  }

  template<class T>
  inline void Arr2D<T>::SetColumn(int c, const std::vector<T> & vec)
  {
    assert(isRange(c, 0, m_W) && m_H == (int)(vec.size()));
    for(int r = 0; r < m_H; r++)
    {
      m_data[r][c] = vec[r];
    }
  }

  template<class T>
  inline void Arr2D<T>::GetColumn(int c, std::vector<T> & vec)
  {
    assert(isRange(c, 0, m_W) && m_H == (int)(vec.size()));
    for(int r = 0; r < m_H; r++)
    {
      vec[r] = m_data[r][c];
    }
  }

	/**
	 * \brief allocates 2D-arr of dimension cx*cy, and copies into it current elements starting at (x,y)
	 * \param x		start column
	 * \param y		start row
	 * \param cx	number of result and copy columns, 0 resuts in usage of all columns form x up to end
	 * \param cy	number of result and copy rows, 0 resuts in usage of all rows form y up to end
	 */
	template<class T>
    inline void Arr2D<T>::Reshape(int x, int y, int cx, int cy) 
	{
		if( cx == 0 ) cx = m_W-x-1;
		if( cy == 0 ) cy = m_H-y-1;
		assert( x+cx < m_W && y+cy < m_H ); //rest is checked in AllocCopySubArray2D
		T **newdata = AllocCopySubArray2D<T>( m_data, x, y, cx, cy );
		m_W = cx;
		m_H = cy;
		m_size = cx*cy;
  		m_externData==0 ? FreeArray2D<T>(m_data) : delete[] m_data;
		m_externData = 0;
		m_data = newdata;
	}

#ifdef __INTEL_COMPILER
template<class T>
template<class F>
inline Arr2D<T>& Arr2D<T>::ScaledAdd( F factor, const Arr2D<T>& src ) {
#else
template<class T>
inline Arr2D<T>& Arr2D<T>::ScaledAdd( double factor, const Arr2D<T>& src ) {
	typedef double F;
#endif
	assert( HasEqualDim( *this, src ) );
	const T* s = src.begin();
	for( T* p = begin(); p != end(); ++p, ++s ) {
		*p = T(*p + factor * *s);
	}
	return *this;
}

template<class T>
inline Point2i Arr2D<T>::ArgMax() const {
	Point2i res;
	T max = std::numeric_limits<T>::is_integer ? 
		std::numeric_limits<T>::min() : -std::numeric_limits<T>::max();
	int plateau; //how many points already have found max/min value
	for( int y = 0; y != m_H; ++y ) {
		for( int x = 0; x != m_W; ++x ) {
			T v = At(x,y);
			if( max < v ) {
				max = v;
				plateau = 1;
				res.x = x;
				res.y = y;
			} else if( max == v ) {
				++plateau;
				if( rand()*plateau <= RAND_MAX ) {
					res.x = x;
					res.y = y;
				}
			}
		}
	}
	return res;
}

template<class T>
inline Point2i Arr2D<T>::ArgMin() const {
	Point2i res;
	T min = std::numeric_limits<T>::max();
	int plateau; //how many points already have found max/min value
	for( int y = 0; y != m_H; ++y ) {
		for( int x = 0; x != m_W; ++x ) {
			T v = At(x,y);
			if( min > v ) {
				min = v;
				plateau = 1;
				res.x = x;
				res.y = y;
			} else if( min == v ) {
				++plateau;
				if( rand()*plateau <= RAND_MAX ) {
					res.x = x;
					res.y = y;
				}
			}
		}
	}
	return res;
}

////////////////////////////////////////////////////////////////////////////
// Derived types.
////////////////////////////////////////////////////////////////////////////

typedef  Arr2D<signed char>     Arr2sb;
typedef  Arr2D<unsigned char>   Arr2ub;

typedef  Arr2D<short>           Arr2s;
typedef  Arr2D<unsigned short>  Arr2us;

typedef  Arr2D<int>             Arr2i;
typedef  Arr2D<unsigned int>    Arr2ui;

typedef  Arr2D<float>           Arr2f;
typedef  Arr2D<double>          Arr2d;

typedef  Arr2D<bool>            Arr2b;

} // namespace YATL

//new recommended
namespace xtd {
	template <class T> 
	class arr2d: public YATL::Arr2D<T> {
		typedef YATL::Arr2D<T> superclass;
	public: //same constructors
		arr2d() {}
		arr2d(int W, int H, T v = T()) : superclass(W, H, v) {}
		arr2d(const superclass & a) : superclass(a) {}

		void clear()
			{ Clear(); }
		void resize(int W, int H, T v = T(), bool bInit = true)
			{ Resize(W, H, v, bInit); }
	};
}

#endif   // ALIB_ARR_2D_H
